package org.example.binary;

public class MySqrt {
    /**
     * 给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
     *
     * 正数的平方根有两个，只输出其中的正数平方根。
     *
     * 如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        //利用二段性可二分，每个数的平方不是小于等于x,就是大于x
        int left = 0,right = x,ret = -1;
        while(left <=right){
            int mid = (left+right)/2;
            if((long)mid*mid <=x){
                ret = mid;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return ret;
    }
}
